#include <pool/pool.h>
#include <functional/assert.h>
#include <compiler/runtime_info.h>
#include "trie.h"

void trie_node_destroy( trie_node* tn );

trie* trie_create()
{
    trie* tr;
    tr = (trie*)palloc( sizeof(trie) );
    assert( tr != NULL );

    tr->cword = 0;
    tr->root = (trie_node*)palloc( sizeof(trie_node) );
    assert( tr->root != NULL );

    tr->root->flag = 0;
    memset( tr->root->child, 0, sizeof(tr->root->child) );

    return tr;
}

int32 trie_insert( trie* tr, const char* word, int32 flag )
{
    const uint8* ptr = (const uint8*)word;
    trie_node* n = tr->root;
    while( *ptr )
    {
        if( n->child[*ptr] == NULL )
        {
            n->child[*ptr] = (trie_node*)palloc( sizeof(trie_node) );
            assert( n->child[*ptr] != NULL );
            n->child[*ptr]->flag = 0;
            memset( n->child[*ptr]->child, 0, sizeof(n->child[*ptr]->child) );
        }
        n = n->child[*ptr];
        ++ptr;
    }
    if( n != tr->root && n->flag == 0 )
    {
        n->flag = flag;
        ++tr->cword;
    }
    return tr->cword;
}

int32 trie_remove( trie* tr, const char* word )
{
    const char* ptr = word;
    trie_node* n = tr->root;
    while( *ptr )
    {
        if( n->child[*ptr] == NULL )
            break;
        n = n->child[*ptr];
        ++ptr;
    }
    if( *ptr == 0 )
    {
        n->flag = 0;
        --tr->cword;
    }
    return tr->cword;
}

char* trie_match( trie* tr, char* src, int32* flag )
{
    const uint8* ptr = (const uint8*)src;
    char* r = NULL;
    trie_node* n = tr->root;
    while( *ptr )
    {
        if( n->child[*ptr] == NULL )
            break;
        n = n->child[*ptr];
        ++ptr;
        if( n->flag != 0 )
        {
            *flag = n->flag;
            r = (char*)ptr;
        }
    }
    return r;
}

void trie_destroy( trie* tr )
{
    trie_node_destroy( tr->root );
    pfree( tr );
}

void trie_node_destroy( trie_node* tn )
{
    int i;
    for( i = 0; i < 26; ++i )
    {
        if( tn->child[i] != NULL )
            trie_node_destroy( tn->child[i] );
    }
    pfree( tn );
}
